package com.leet.code.simple_array;

/**
 * @description:
 * @author: WYG
 * @time: 2020/12/24 14:39
 */

public class NumSmallerByFrequency {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        //首先获取两个字符串数组的长度,用于创建存储对应字母出现频次的新数组
        int queries_size = queries.length;
        int word_size = words.length;
        //根据每个数组中字符的个数创建结果数组
        int[] queries_num = new int[queries_size];
        int[] word_num = new int[word_size];
        //统计queries数组中对应字符串的最小字母出现频次,并统计出现次数
        for (int i = 0; i < queries_size; i++) {
            char[] chars = queries[i].toCharArray();
            char min = 'z';
            //先统计出最小字符
            for (int j = 0; j < chars.length; j++) {
                if (chars[j] < min) {
                    min = chars[j];
                }
            }
            //然后计数
            for (char c : chars) {
                if (c == min) {
                    queries_num[i]++;
                }
            }
        }
        //统计words数组中对应字符串的最小字母出现频次,并统计出现次数
        for (int m = 0; m < word_size; m++) {
            char[] chars = words[m].toCharArray();
            char min = 'z';
            //先统计出最小字符
            for (int n = 0; n < chars.length; n++) {
                if (chars[n] < min) {
                    min = chars[n];
                }
            }
            //然后计数
            for (char c : chars) {
                if (c == min) {
                    word_num[m]++;
                }
            }
        }
        //使用queries数组存放最终的结果
        for (int a = 0; a < queries_size; a++) {
            //存储words数组中的每个字符串字母出现频次大于queries数组中字符串的个数
            int temp = 0;
            for (int b = 0; b < word_size; b++) {
                if (queries_num[a] < word_num[b]) {
                    temp++;
                }
            }
            queries_num[a] = temp;
        }
        //返回结果
        return queries_num;
    }

        public int[] new_numSmallerByFrequency(String[] queries, String[] words) {
            //count用于统计words中所有单词的最小字母出现次数，
            //大小设置为12是为了避免下面进行判定的时候出现越界而做的冗余处理
            int[] count = new int[12];
            for (String word:words)
                count[counts(word)]++;
            //计算后缀和，现在count[i]表示最小字母出现次数大于或等于i的单词总数。
            for (int i=9;i>=0;i--)
                count[i]+=count[i+1];
            //结果数组
            int[] result = new int[queries.length];
            //遍历queries中的每个字符串，利用前面计算得到的count数组，可以直接得到答案。
            for (int i=0;i<queries.length;i++)
                result[i]=count[counts(queries[i])+1];
            return result;
        }

        //counts方法用于统计字符串s中最小字母出现的次数
        private int counts(String s){
            char c = s.charAt(0);
            int count = 1;
            for (int i=1;i<s.length();i++){
                char temp = s.charAt(i);
                if (temp==c)
                    count++;
                else if (temp<c){
                    c=temp;
                    count=1;
                }
            }
            return count;
        }

}
